/** 自定义一个二叉树，填入数据，然后通过中序遍历打印出来 */

/** 下面方法形成的树结构
 *      0
 *    1   2
 * 3        4
 */
/** 定义数据sturct */
function Node(val) {
  this.val = val;
  this.lChild = this.rChild = null;
}

/** 插入值，key % 2 这个判断有待商榷 */
function insertToTree(root, key) {
  if(root == null) return new Node(key);
  if (key % 2) {
    root.lChild = insertToTree(root.lChild, key)
  } else {
    root.rChild = insertToTree(root.rChild, key)
  }
  return root;
}

/** 中序遍历（左中右） */
function inOrder(root) {
  if (root == null) return;
  inOrder(root.lChild)
  console.info(root.val)
  inOrder(root.rChild)
  return;
}

/** 前序遍历（中左右）
 * 
 *  可以知道，第一个数是根节点 
*/
function preOrder(root) {
  if (root == null) return;
  console.info(root.val)
  inOrder(root.lChild)
  inOrder(root.rChild)
  return;
}

/** 执行的主方法 */
function main() {
  let root = null;
  for (let i = 0;i<5;i++) {
    root = insertToTree(root, i)
  }
  inOrder(root)
  preOrder(root)
}

main();


/** 可以从前序、中序的结合还原树struct
 * 1.前序的第一个是根节点
 * 2.拿这这个根节点在中序里找到节点位置
 * 3.中序中，根节点位置的左边是左节点、右侧是右节点。
 * 4.两个再结合找到最终的树struct
 */